#pragma once
#include <assert.h>
#include <iostream>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
  AVLTreeNode(pair<K, V> kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_bf(0)
    ,_kv(kv)
  {}
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  int _bf;  //balance factor 平衡因子
  pair<K, V> _kv;
};


template<class K, class V>
class AVLTree 
{
  typedef AVLTreeNode<K, V> Node;
  public:
  AVLTree()
  :_root(nullptr)
  {}

  bool insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
    }
    else {
      Node* parent = nullptr;
      Node* cur = _root;
      while (cur)
      {
        if (kv.first < cur->_kv.first)
        {
          parent = cur;
          cur = cur->_left;
        }
        else if (kv.first > cur->_kv.first)
        {
          parent = cur;
          cur = cur->_right;
        }
        else 
        {
          return false;
        }
      }
      cur = new Node(kv);
      if (kv.first < parent->_kv.first)
      {
        parent->_left = cur;
        cur->_parent = parent;
      }
      else if (kv.first > parent->_kv.first)
      {
        parent->_right = cur;
        cur->parent = parent;
      }
  
      //1.更新平衡因子 -- 新增结点到祖先结点的路径上的结点
      //2.若出现异常平衡因子，则需要旋转平衡处理
      while (parent)
      {
        if (cur == parent->_right)
        {
          parent->_bf++;
        }
        else 
        {
          parent->bf--;
        }
        //这里存在四种情况 
        //1.平衡因子大于1 或 小于-1 需要进行旋转平衡 
        //2.父亲的平衡因子等于0 这说明了这个一定是补上了子树矮的那一部分，子树的最大高度不变，无需继续向上调整
        //3.父亲平衡因子为1 或者 -1 说明子树有一边变高了，这棵树最大高度改变，需继续向上调整
        //4.父亲不存在了，一路更新到根节点
        if (parent->_bf == 2 || parent->_bf == -2) 
        {
  
        }
        else if (parent->_bf == 0)
        {
          break;
        }
        else if (parent->_bf == 1 || parent->_bf == -1)
        {
          cur = parent;
          parent = parent->_parent;
        }
        else 
        {
          //插入更新平衡因子前，就有问题了
          assert(false);
        }
      }
      return true;
  
  }
  }
  private:
  Node* _root;
};
